/**
 * Starting at the 0 (zero) index, you need to "jump" through a one-dimensional
 * array (zero based index) of true/false values. True is a place you can land
 * on (if desired) and false is a place you must jump over (cannot land on). The
 * array can be very very long.
 * 
 * Your "velocity" indicates how many spots (or array indexes) you advance with
 * every jump. For example, if you have a velocity of 2 and are currently at
 * index 4, after the jump, you will be at index 6. Before each jump you can
 * increase your velocity by 1, decrease your velocity by 1, or keep the same
 * velocity. You can only go forwards.
 * 
 * You start at index 0 (zero), with a velocity of 1. This means that for the
 * very first jump, you can keep the same velocity and move to index 1, or
 * increase velocity by 1 (to a velocity of 2) to move to index 2. On this first
 * jump, you can't decrease your velocity as that would make your velocity 0
 * (zero) and you wouldn't move. Now that you've jumped, you can again increase,
 * decrease, or keep your velocity the same, then jump again.
 * 
 * As an example, let's say you increased your velocity to 2 and jumped. You're
 * now at index 2 with a velocity of 2. You can: 1) decrease your velocity to 1
 * and jump to index 3. 2) keep your velocity at 2 and jump to index 4. 3)
 * increase your velocity to 3 and jump to index 5.
 * 
 * Remember, you can only and on an index if it's "true". You are successful if
 * you can get past the last index. Implement a function to determine if the
 * rabbit can make it across given the field (array).
 * 
 * Here is a field that the rabbit cannot cross: $field = array(true, true,
 * false, true, false, true, false, false, false, true);
 * 
 * Here is a field that the field can cross: $field = array(true, true, false,
 * true, false, true, true, false, false, true, false);
 * 
 * http://www.careercup.com/question?id=5640356599169024
 * 
 * @author ruinvepc
 * 
 */
public class JumpingRabbit {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        /* false */
        new JumpingRabbit(new boolean[] { true, true, false, true, false, true,
                false, false, false, true });
        /* true */
        new JumpingRabbit(new boolean[] { true, true, false, true, false, true,
                true, false, false, true, false });
        /* true */
        new JumpingRabbit(new boolean[] { true, true, true, true, false, true,
                true, true, true, true, true, true, true, true, true, true,
                true, true, true, true, true, true, true, true, true, true,
                true, true, true, true, true });

    }

    private boolean[] steps;

    public JumpingRabbit(boolean[] steps) {
        this.steps = steps;
        System.out.println("Can pass: " + canPass(0, 1));
    }

    public boolean canPass(int idx, int speed) {
        if (idx >= steps.length)
            return true;
        if (steps[idx]) {
            boolean canPass = canPass(idx + speed, speed);
            if (!canPass && idx > 0) {
                canPass = canPass(idx + speed + 1, speed + 1);
                if (!canPass && idx > 1 && speed > 1) {
                    canPass = canPass(idx + speed - 1, speed - 1);
                }
            }
            return canPass;
        }
        return false;
    }

}
